Hema Dubey ¹, Nilay Khare ¹, K. K. Appu Kuttan ¹, Shreyas Bhatia ²

Affiliations
1 Department of Computer Science and Engineering, Maulana Azad National Institute of Technology, Bhopal - 462003, Madhya Pradesh, IN
2 Adobe Systems, Noida – 201304, IN

Abstract

Background/Objectives: PageRanking algorithm is a well known link based technique given by Google for indexing of its web pages. This algorithm works on the linking structure of web pages id est inbound and outbound links of pages. The existing Page Rank algorithm follows equal distribution law that is; it distributes the Page Rank of a web page evenly among all the outgoing links. The problem with the uniform distribution of Page Rank is that sometimes uninteresting pages got high Page Rank values. Methods/Statistical Analysis: This paper proposed an improved parallel Page Rank algorithm that un-uniformly distributes the Page Rank values among all the outgoing links. The proposed work has been implemented on NVIDIA Quadro 2000 GPU architecture using CUDA programming language. Findings: The proposed algorithm mitigates spam and provides better results in terms of computational time as compared to Parallel Page Rank, because it assigns higher priority to important pages and less priority to less important web pages. By assigning values in such a fashion important pages show an increase in the Page Rank value and unrelated pages that is spam pages show a decrease in Page Rank value. Application: The proposed work performs spam filtering by classifying important as well as irrelevant web pages.

Keywords

CUDA, GPU, Non-Uniform Distribution, Parallel Page Rank, Spam Pages.

Full Text

   

Dhirendra Pratap Singh ¹, Nilay Khare ¹

Affiliations
1 Department of Computer Science and Engineering, Maulana Ajad National Institute of Technology, Bhopal - 462003, Madhya Pradesh, IN

Abstract

The objective of this research is to propose and implement a fast parallel Single source shortest path (SSSP) algorithm on Graphics Processing Unit (GPU) based highly parallel and cost effective platform for dense and complete graphs. The proposed algorithm is a variant of Dijkstra’s algorithm for SSSP calculation for complete and dense graphs. In place of relaxing all the edges of a selected node as in Dijkstra’s algorithm, it relaxes one-one selected edge of different nodes of the graph simultaneously at any iteration. This paper shows parallel implementation of both Dijkstra’s algorithm and our modified Dijkstra’s algorithm on a GPU-based machine. We evaluate these implementations on NVIDIA Tesla C2075 GPU- based machines. Parallel implementation of proposed modified Dijkstra’s algorithm gives a two to three times speed increase over a parallel Dijkstra’s algorithm on a GPU-based machine for complete and dense graphs. The proposed algorithm has minimized the number of edges relaxed by one parallel thread at any iteration of parallel Dijkstra’s algorithm.

Keywords

CUDA, Graph Algorithm, GPU Computing, Parallel Dijkstra’s Algorithm, Parallel Single Source Shortest Path Algorithm.

Full Text

   

Jaideep Patel ¹, Nilay Khare ¹

Affiliations
1 Department of Computer Science and Engineering, Maulana Azad National Institute of Technology, Bhopal – 462003, Madhya Pradesh, IN

Abstract

Background/Objectives: Congestion in wireless network causes loss of packets, longer delay and throughput degradation. So it is always a major concern to network. Many sources send data of different priorities in different applications like Multimedia. So weighted fairness for these applications is also required. Methods: To address these issues we propose a protocol named FPECODA for Mobile Ad hoc Network. Findings: It uses the GPU for parallel version of algorithm for finding the Dynamic Priority of packets, sorting algorithm etc. It also applies the fuzzy logic for rate control of node. Subsequently handling the congestion will become more effective by: a) Bottleneck node based source data sending rate control. b) Flexible Queue Scheduler for packets transfer. Improvements: Experimental results demonstrate that processing of packets becomes significantly faster than CPU only based algorithm. Also it will be very efficient in terms of throughput, end to end delay and fairness in network.

Keywords

Congestion Control, GPU, Multimedia, Parallel Computation, Multiple Class of Traffic

Full Text